package myself.a010BinaryTreeRecursion;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/27
 * Time 21:14
 * Mail 739153436@qq.com
 */
public class IsBST {

    // 是否是搜索二叉树判断
    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }

        return process(head).isBST;
    }

    private static Info process(Node head) {
        if (head == null) {
            return null;
        }
        Info left = process(head.left);
        Info right = process(head.right);

        // isBST,这个信息的传递非常关键，使得正确与否的判断一直在方法栈中传递
        boolean isBST = false;
        int max = head.value;
        int min = head.value;
        // 这里的比较也是需要注意的，是取出整个范围的最值
        if (left != null) {
            max = Math.max(max, left.max);
            min = Math.min(min, left.min);
        }
        if (right != null) {
            max = Math.max(max, right.max);
            min = Math.min(min, right.min);
        }
        if (
                (left == null ? true : (isBST && left.max < head.value))
                        &&
                        (right == null ? true : (isBST && right.min > head.value))
        ) {
            isBST = true;
        }
        return new Info(max, min, isBST);
    }

    public static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        public int max;
        public int min;
        public boolean isBST;

        public Info(int max, int min, boolean isBST) {
            this.max = max;
            this.min = min;
            this.isBST = isBST;
        }
    }
}
